package com.zdj;

/**
 * @author zhangdj
 * @date 2021-10-18 18:54:38
 * 获取三角形二维数组的到达最底层最短路径
 * 1
 * 2 3
 * 4 5 6
 */
public class MainPathTriangle {

    public static void main(String[] args) {
        int[][] arr = new int[][]{{1}, {2, 3}, {4, 0, 6}};
        System.out.println(getMinPath(arr));
    }

    public static int getMinPath(int[][] arr) {
        if (arr == null) {
            return 0;
        }
        return getMinPath(arr, 0, 0);
    }

    public static int getMinPath(int[][] arr, int i, int j) {
        int oneLength = arr.length;
        if (i == oneLength - 1) {
            return arr[i][j];
        }
        return arr[i][j] + Math.min(getMinPath(arr, i + 1, j), getMinPath(arr, i + 1, j + 1));
    }
}
